csp 2023-12 树上搜索

Southea Lv1
  2024-04-01 2024-04-01 Created   2024-04-01 16:47:34 2024-04-01 16:47:34 Updated    

1.20分

各个类别的权重相等，且每个类别的上级类别都是根类别；

我编的样例（只构造了树，没有添加进行询问的数据）：

1
2
3
5 5
10 10 10 10 10
1 1 1 1

需要注意的是，循环结束的条件是剩下一个类别，因此若输入的测试类别是1，输出应该是2 3 4 5（不包含1，考试时没注意到这点，只拿了10分）；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    int weight[n + 1];
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> weight[i];
        sum += weight[i];
    }
    int up[n];
    for (int i = 1; i < n; i++)
        cin >> up[i];
    for (int i = 0; i < m; i++)
    {
        int val;
        cin >> val;
        if (val == 1)
            for (int j = 2; j <= n; j++)
                cout << j << ' ';
        else
            for (int j = 2; j <= val; j++)
                cout << j << ' ';
        cout << endl;
    }
}

2.另外20分

每个类别的权重相等，且每个类别至多有一个下级类别；

我编的样例（只构造了树，没有添加进行询问的数据）：

1
2
3
5 4
10 10 10 10 10
3 1 5 2

特地将编码的索引打乱，体现寻找$$w_s$$最小值时，不能从1-n遍历，寻找最先遇到的最小值，而应该将多个最小值的索引也取min：

1
2
3
4
5
6
7
8
9
10
11
long long mins = 1e10;
for (auto &it : tmp_m) // 计算最小的w
{
	if (mins > abs(it.second.s_w * 2 - tmp_all_weight))
	{
		mins = abs(it.second.s_w * 2 - tmp_all_weight);
        min_i = it.first;
    }
    else if (mins == abs(it.second.s_w * 2 - tmp_all_weight))
        min_i = min(min_i, it.first);
}

3.AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>

using namespace std;
const int N = 2010;
const int M = 110;

// 权重--long long
struct node
{
    long long weight;  // 权重
    int upper;         // 父类
    long long s_w;     // 它和其全部后代类别的权重之和
    map<int, node> ss; // 子类，没有维持ss中的ss的值
    int num_s;         // 算上自己和子类的节点总数
    node()
    {
        weight = 0;
        upper = 0;
        s_w = 0;
        num_s = 1;
    }
    node(long long w)
    {
        weight = w;
        upper = 0;
        s_w = w;
        num_s = 1;
    }
};

map<int, node> maps;  //   key：索引/类别   value：节点属性
long long all_weight; // 所有节点的权重之和
int all_node;

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        long long tmp;
        cin >> tmp;
        maps.insert(pair<int, node>(i, node(tmp)));
        all_weight += tmp;
    }
    for (int i = 2; i <= n; i++)
    {
        int tmp_p;
        cin >> tmp_p;
        maps[i].upper = tmp_p;
        maps[tmp_p].ss.insert(pair<int, node>(i, maps[i]));
    }
    // 维护权重和
    for (int i = 1; i <= n; i++)
    {
        queue<int> q;
        q.push(i);
        while (q.size() != 0)
        {
            int tt = q.front();
            q.pop();
            for (auto &j : maps[tt].ss)
            {
                maps[i].s_w += j.second.weight;
                maps[i].num_s++;
                q.push(j.first);
            }
        }
    }
    all_node = n;
    for (int i = 0; i < m; i++)
    {
        int val;
        cin >> val;

        int min_i;
        map<int, node> tmp_m = maps;
        long long tmp_all_weight = all_weight;
        int tmp_all_node = all_node;
        // 开始循环
        while (tmp_all_node != 1)
        {
            long long mins = 1e10;
            for (auto &it : tmp_m) // 计算最小的w
            {
                if (mins > abs(it.second.s_w * 2 - tmp_all_weight))
                {
                    mins = abs(it.second.s_w * 2 - tmp_all_weight);
                    min_i = it.first;
                }
                else if (mins == abs(it.second.s_w * 2 - tmp_all_weight))
                    min_i = min(min_i, it.first);
            }
            cout << min_i << " "; // 输出最小w对应的类别
            // find 后代中有无val
            queue<int> q;
            q.push(min_i);
            bool find_val = false;
            while (q.size() != 0)
            {
                int tt = q.front();
                q.pop();
                if (tt == val)
                {
                    find_val = true;
                    break;
                }
                for (auto &u : tmp_m[tt].ss)
                    q.push(u.first);
            }
            if (find_val) // 在后代类别中
            {
                map<int, node> tmp_mm = tmp_m;
                tmp_m.clear();
                queue<int> q;
                q.push(min_i);
                while (q.size() != 0)
                {
                    int tt = q.front();
                    q.pop();
                    tmp_m.insert(pair<int, node>(tt, tmp_mm[tt]));
                    for (auto &u : tmp_mm[tt].ss)
                        q.push(u.first);
                }
                tmp_m[min_i].upper = 0;
                tmp_all_weight = tmp_m[min_i].s_w;
                tmp_all_node = tmp_m[min_i].num_s;
            }
            else
            {                                // 既不在后代类别中，本身也不是正确类别
                if (tmp_m[min_i].upper != 0) // 先在上层节点的后续节点中删除
                {
                    tmp_m[tmp_m[min_i].upper].ss.erase(min_i);
                    // 更新权重
                    int tmp_upper = tmp_m[min_i].upper;
                    while (tmp_upper != 0)
                    {
                        tmp_m[tmp_upper].s_w -= tmp_m[min_i].s_w;
                        tmp_m[tmp_upper].num_s -= tmp_m[min_i].num_s;
                        tmp_upper = tmp_m[tmp_upper].upper;
                    }
                }
                tmp_all_weight -= tmp_m[min_i].s_w;
                tmp_all_node -= tmp_m[min_i].num_s;
                // 删除该节点以及后续节点
                queue<int> q;
                q.push(min_i);
                while (q.size() != 0)
                {
                    int tt = q.front();
                    q.pop();
                    for (auto &u : tmp_m[tt].ss)
                        q.push(u.first);
                    tmp_m.erase(tt);
                }
            }
        }
        cout << endl;
    }
}

出错：

维护权重时试图从n-1遍历枚举，事实是编号大的节点不一定是叶子节点，debug样例：

1
2
3
5 4
10 10 10 10 10
3 1 5 2

另一个编的样例：

1
2
3
11 100
10 100 100 50 10 20 10 20 30 10 40 
1 1 1 2 2 3 3 3 8 10

The END！

  • Title: csp 2023-12 树上搜索
  • Author: Southea
  • Created at : 2024-04-01 00:00:00
  • Updated at : 2024-04-01 16:47:34
  • Link: https://southea.github.io/2024/04/01/csp 2023-12 树上搜索/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
csp 2023-12 树上搜索
  1. 1.20分
  2. 2.另外20分
  3. 3.AC代码